package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.ListNode;

import java.util.HashSet;

/**
 * [141]环形链表.java
 * <p>
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 * <p>
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
 */
public class Lc121 {
    public static void main(String[] args) {

    }

    /**
     * 暴力法
     * 时间复杂度n^2
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int i1 = i + 1; i1 < prices.length; i1++) {
                int temp = prices[i1] - prices[i];
                max = Math.max(max, temp);
            }
        }
        return max;
    }

    /**
     * 巧妙思路，遍历中要么低于最低价格没有利润，要么高于最低价格有利润，只要比最大利润高，则替换
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        int lowestPrice = Integer.MAX_VALUE;
        int max = 0;
        for (int price : prices) {
            if (lowestPrice > price) {
                lowestPrice = price;
            } else if (price - lowestPrice > max) {
                max = price - lowestPrice;
            }
        }
        return max;
    }


}
